1. Field
Embodiments of the invention relate to creating and maintaining an order of a log stream without the use of a lock or latch.
2. Description of the Related Art
Databases store and retrieve data. Relational databases are organized into tables that consist of rows and columns of data. The rows may be called tuples or records or rows. A database typically has many tables, and each table typically has multiple records and multiple columns.
A table in a database can be accessed using an index. An index is an ordered set of references (e.g., pointers) to the records in the table. The index is used to access each record in the table using a key (i.e., one of the fields or attributes of the record, which corresponds to a column). The term “key” may also be referred to as “index key”. Without an index, finding a record may require a scan (e.g., linearly) of an entire table. Indexes provide an alternate technique to accessing data in a table. Users can create indexes on a table after the table is built. An index is based on one or more columns of the table. Also, a table may use hashing or some other mechanism that eliminates the need for an index.
A query may be described as a request for information from a database based on specific conditions. A query typically includes one or more predicates. A predicate may be described as an element of a search condition that expresses or implies a comparison operation (e.g., A=3).
Database systems provide for data consistency, transaction commit and abort, and recoverability in the event of a failure log changes made to database objects (e.g., tables). When a database system allows for concurrency of updates, the component responsible for managing the logged data determines how the log records are sequenced so that each log record can be uniquely identified and found. The simplest way to accomplish this is for the log managing component to serialize all requests to write a log record so that at any given moment in time only one log record is being added to the stream of log records. Typically, this serialization is facilitated through means of a lock or latch or similar mechanism (henceforth referred to generically as a latch). However, this level of serialization can become a bottleneck to all transactions making database updates.
In order to avoid this bottleneck, conventional systems offer various techniques. A first technique is using a single sequence number that is unique and not having to worry about the exact physical ordering of the log records. This makes the serialization very simple at the expense of making it difficult to find a particular log record. A second technique queues all requests to a single execution unit with the possibility of putting the entire log record on the queue. The advantages and disadvantages are similar to the first technique. A third technique reserves ranges of log records for multiple execution units and merges the records together at a later time. The complication again comes when an individual log record needs to be located for some purpose. Other techniques use variations on the first, second, and third techniques.
Some conventional systems rely on exact sequencing of the log records in the physical stream of log records. The Relative Byte Address (RBA) of a log record, which is an address relative to the beginning of the log stream, and the Logical Record Sequence Number (LRSN) are both increasing, although there could be multiple log records with the same LRSN value that only have increasing RBA values. The exact sequencing makes it very easy to locate a log record, but imposes limitations on the serialization technique used to place an individual log record in the stream of log records. In addition, the necessity of having to control Input/Output (I/O) of the log stream at the block level, which is often not necessary for some database systems, induces further complications and additional structures that need to be properly updated and kept in sequence. For this reason, and due to the desire to have the expense of placing the log record in the log stream charged to the requesting application, some conventional systems have serialized all requests so that the contention is on a single latch that controls the creation of the log stream.
Thus, there is a need for creating and maintaining the order of a log stream without the use of a lock or latch.